/**
 * 给定一个包含n + 1 个整数的数组nums ，其数字都在[1, n]范围内（包括 1 和 n），可知至少存在一个重复的整数。
 *
 * 假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
 *
 * 你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
 *
*思路：二分查找（鸽子巢原理）忘记了可以看https://leetcode.cn/problems/find-the-duplicate-number/solution/xun-zhao-zhong-fu-shu-by-leetcode-solution/
 */
class FindDuplicate {
    public int findDuplicate(int[] nums) {
        int len=nums.length;
        int left=1;
        int right=len-1;
        int ans=-1;
        while(left<=right){
            int count=0;
            int mid=left+((right-left)>>>1);
            for(int x:nums){
                if(x<=mid){
                    count++;
                }
            }
           if(count<=mid){
               left=mid+1;
           }else{
               ans=mid;
               right=mid-1;
           }
        }
        return ans;
    }
}